/// Source : https://leetcode.com/problems/minimize-malware-spread-ii/
/// Author : liuyubobobo
/// Time   : 2018-10-20

#include <iostream>
#include <vector>

using namespace std;


/// Brute Force
/// Time Complexity: O(len(initial) * v^2)
/// Space Complexity: O(v)
class Solution {

private:
    int n;

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

        n = graph.size();
        sort(initial.begin(), initial.end());

        int res = -1, best = INT_MAX;
        for(int v: initial) {
            int num = try_remove(graph, v, initial);
            if(num < best){
                best = num;
                res = v;
            }
        }
        return res;
    }

private:
    int try_remove(const vector<vector<int>>& g, int v, const vector<int>& initial){

        vector<bool> visited(n, false);
        int res = 0;
        for(int u: initial)
            if(u != v && !visited[u])
                res += dfs(g, u, v, visited);
        return res;
    }

    int dfs(const vector<vector<int>>& g, int u, int v, vector<bool>& visited){

        visited[u] = true;

        int res = 1;
        for(int i = 0; i < n; i ++)
            if(g[u][i] && i != v && !visited[i])
                res += dfs(g, i, v, visited);
        return res;
    }

};


int main() {

    vector<vector<int>> g1 = {{1,1,0,0},{1,1,1,0},{0,1,1,1},{0,0,1,1}};
    vector<int> initial1 = {3,0};
    cout << Solution().minMalwareSpread(g1, initial1) << endl;
    // 0

    vector<vector<int>> g2 = {
            {1,0,0,0,0,0,0,0,0},
            {0,1,0,0,0,0,0,0,0},
            {0,0,1,0,1,0,1,0,0},
            {0,0,0,1,0,0,0,0,0},
            {0,0,1,0,1,0,0,0,0},
            {0,0,0,0,0,1,0,0,0},
            {0,0,1,0,0,0,1,0,0},
            {0,0,0,0,0,0,0,1,0},
            {0,0,0,0,0,0,0,0,1}};
    vector<int> initial2 = {6,0,4};
    cout << Solution().minMalwareSpread(g2, initial2) << endl;
    // 0

    return 0;
}